package bin_tree;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
 * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
 */
public class NumJZ36_ConvertTree {
   private class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };
   Node tail;
    public Node treeToDoublyList(Node root) {
       if(root==null){
           return null;
       }
       //treeToDoublyListHelper（）：求双向有序列表
       Node head=treeToDoublyListHelper(root);
       //连接首尾
       head.left=tail;
       tail.right=head;
       return head;
    }
    public Node treeToDoublyListHelper(Node root) {
        if(root==null){
            return null;
        }
        //对二叉树进行中序遍历：保证顺序。
        //递归函数进行的操作是二叉树变为双向链表
        Node leftHead=treeToDoublyListHelper(root.left);
        Node leftTail=leftHead;
        //找左子树尾节点
        while(leftTail!=null&&leftTail.right!=null){
            leftTail=leftTail.right;
        }
        //此时leftTail是左子树尾节点
        if(leftTail!=null){
            leftTail.right=root;
            root.left=leftTail;
        }
        //左子树连接完毕
        //处理右边
        Node rightHead=treeToDoublyListHelper(root.right);
        if(rightHead!=null){
            rightHead.left=root;
            root.right=rightHead;
        }
        tail=rightHead;
        while(tail!=null&&tail.right!=null){
            tail=tail.right;//走完tail是尾节点
        }
        if(tail==null){
            tail=root;
        }
        //返回大链表的根节点(头节点)：两种情况
        //左树为空返回root，不为空返回左树头节点
        return leftHead==null?root:leftHead;
    }
}
